package com.kehao.newcoder;

import org.junit.Test;

public class NC32Solution {
    /**
     * 牛顿迭代法
     * @param x
     * @return
     */
    public int sqrt (int x) {
        // write code here
        if(x==0||x==1) return x;
        long result = x/2;
        while (!(result*result<=x&&(result+1)*(result+1)>x)){
            long y0 = result*result - x;
            result = (result*result*2-y0)/(result*2);
        }
        return (int) result;
    }

    public int sqrt1(int x){
        if(x==0||x==1) return x;
        int result = x/2;
        int min = 0,max=result;
        while (true){
            int ans = result*result;
            if(ans==x) return result;
            int large = (result+1)*(result+1);
            if(ans<x&&large>x){
                return result;
            }
            if(ans>x){
                max = result;
            }
            if(ans<x){
                min = result;
            }
            result = (min+max)/2;
        }
    }

    @Test
    public void test(){
        int sqrt = sqrt(909520789);
        System.out.println(sqrt);
    }
}
